package ai.zixing.mashibing.advance_class.secend.class02;

import java.util.HashMap;

/**
 * 给定一个整数组成的无序数组arr，值可能正、可能负、可能0
 * 给定一个整数值K
 * 找到arr的所有子数组里，哪个子数组的累加和等于K，并且是长度最大的
 * 返回其长度
 */
public class Code02_LongestSumSubArrayLength {

    public static void main(String[] args) {
        int testTime = 100000;
        int maxSize = 20;
        int maxValue = 30;
        System.out.println("begin test");
        for (int i = 0; i < testTime; i++) {
            int[] arr = generatorArray(maxSize, maxValue);
            int k = (int) (Math.random() * maxValue) + 1;
            int ans1 = maxLength(arr, k);
            int ans2 = right(arr, k);
            if (ans2 != ans1) {
                System.out.println("error");
                break;
            }
        }
        System.out.println("test end");
    }

    private static int maxLength(int[] arr, int k) {
        if (arr == null || arr.length < 1) {
            return 0;
        }
        // 累加和，key-累加和，value-最早出现的下标
        HashMap<Integer, Integer> map = new HashMap<>();
        // 必须先预制一个和为 0 的下标为 -1，任何数 + 0 = 本身，如果不预制 0 元素会影响子数组长度
        map.put(0, -1);
        int sum = 0;
        int len = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            // 前缀和最早出现 sum - k，则
            if (map.containsKey(sum - k)) {
                len = Math.max(i - map.get(sum - k), len);
            }
            // sum 在 map 中不存在，才存入 map
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
        }
        return len;
    }

    private static int right(int[] arr, int k) {
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                // 和等于 k
                if (valid(arr, i, j, k)) {
                    max = Math.max(max, j - i + 1);
                }
            }
        }
        return max;
    }

    private static boolean valid(int[] arr, int L, int R, int k) {
        int sum = 0;
        for (int i = L; i <= R; i++) {
            sum += arr[i];
        }
        return sum == k;
    }

    private static int[] generatorArray(int maxSize, int maxValue) {
        int[] ans = new int[(int) (Math.random() * maxSize) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (int) (Math.random() * maxValue) - (int) (Math.random() * maxValue);
        }
        return ans;
    }
}
